A Fast Fourier Transform (FFT) is, as the name suggests, a fast way to perform a Fourier transform of time-series or other sequential data. It exploits symetries in the cacklulatio of the Fourier transform in order to reuse intermeidate results. Whereas a brute force version of Fourier transform is quandratic in the size of gthe input (N2), the FFT is log-linear (N log2N). For example, for N=1024, FFT is around 100 times faster (1024/log2(1024)).
Used on page 317
Also known as FFT